package sorting

import "gitee.com/guuzaa/sorting/constraints"

func QuickSort[T constraints.Ordered](arr []T) []T {
	quickSort(arr, 0, len(arr)-1)
	return arr
}

func quickSort[T constraints.Ordered](arr []T, low, high int) {
	if low < high {
		split := partition(arr, low, high)
		if split > 1 {
			quickSort(arr, low, split-1)
		}
		quickSort(arr, split+1, high)
	}
}

func partition[T constraints.Ordered](arr []T, low, high int) int {
	pivot := low

	for {
		for low <= high && arr[low] <= arr[pivot] {
			low++
		}

		for low <= high && arr[high] >= arr[pivot] {
			high--
		}

		if low > high {
			break
		} else {
			arr[low], arr[high] = arr[high], arr[low]
		}
	}

	arr[pivot], arr[high] = arr[high], arr[pivot]

	return high
}
